package algorithm;

import java.util.Arrays;

/**
 * @Description:希尔排序
 * @Author: hmm
 * @CreateDate: 2019/8/27
 * @UpdateUser:
 * @UpdateDate: 2019/8/27
 * @UpdateRemark: 修改备注
 * @Version: 1.0
 */
public class ShellSort {
    public static int[] shellSort(int[] array) {
        int len = array.length;
        if(len == 0)
            return array;
        int current, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                current = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > current) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = current;
            }
            gap /= 2;
        }
        return array;
    }

    public static void main(String[] args) {
        int[] arr = {1,6,2,41,11,25,8,31,25,22};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
